package 回溯法;

import java.util.ArrayList;
import java.util.List;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : 分解数字
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/5/18 14:51
 */
public class 背包分解 {
    static int[] w = {1, 2, 3, 4, 5, 6};

    static int rd(int S, int n) {
        if (S == 0) {
            return 1;
        }
        if (S < 0 || S > 0 && n < 0) {
            return 0;
        }
        if (rd(S - w[n], n) == 1) {
            System.out.print(w[n] + "\t");
            return 1;
        }
        return rd(S, n - 1);
    }

    static int rd1(int S, int n, List<Integer> path) {
        if (S == 0) {
//            System.out.println(new ArrayList<>(path));
            return 1;
        }
        if (S < 0 || S > 0 && n < 0) {
            return 0;
        }
        for (int i = n; i >= 0 && (path.size() == 0||w[i] > path.get(path.size() - 1)  ); i--) {
            if (S - w[i] >= 0) {
                path.add(w[i]);
                rd1(S - w[i], n, path);
                path.remove(path.size() - 1);
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        rd(10, 5);
        rd1(10, 5, new ArrayList<>());
    }
}
